import java.util.*;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/19 9:49
 * @description:
 */
public class Solution210 {
    List<List<Integer>> edges = new ArrayList<>();
    int[] inDegrees;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        int index = 0;
        if (prerequisites.length == 0) {
            for (int i = 0; i < numCourses; i++) {
                res[index++] = i;
            }
            return res;
        }
        inDegrees = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int next = prerequisites[i][0];
            int pre = prerequisites[i][1];
            edges.get(pre).add(next);
            inDegrees[next]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) {
                q.add(i);
            }
        }
        int count = 0;

        while (!q.isEmpty()) {
            int u = q.poll();
            res[index++] = u;
            count++;
            for (Integer v : edges.get(u)) {
                inDegrees[v]--;
                if (inDegrees[v] == 0) {
                    q.offer(v);
                }
            }
        }
        if (count != numCourses) {
            return new int[0];
        }
        return res;
    }

    public static void main(String[] args) {
        Solution210 solution = new Solution210();
//        System.out.println(Arrays.toString(solution.findOrder(2, new int[][]{{1, 0}})));
//        System.out.println(Arrays.toString(solution.findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
//        System.out.println(Arrays.toString(solution.findOrder(1, new int[][]{})));
        System.out.println(Arrays.toString(solution.findOrder(2, new int[][]{{0, 1}, {1, 0}})));//存在环
        System.out.println(Arrays.toString(solution.findOrder(3, new int[][]{{1, 0}, {1, 2}, {0, 1}})));//存在环
    }
}
